3D simulation has known a great success during the last three decades in various and large audiences of users: from engineers verifying how a system in design stage will behave in reality, to scientists exploring or demonstrating theoretical conceptions, to general public playing video games or enjoying 3D animation films. 3D simulation knows many evolutions over the past three decades and is still having a growing momentum. Especially, 3D simulation aims at answering users' needs for more complex and more realistic behaviors (Multi-Body Rigid Dynamics, Human Simulation, Cloth Simulation, Particle Simulation . . . ), for wider populations and typologies of objects and for wider scale.
3D simulation has to meet real-time requirements, which was more particularly initiated in the video game industry, by developing specific technologies to support a massive number of users interacting in large scale virtual worlds. A real-time response has to be offered at any time to the connected users, regardless of their number, and regardless of the induced computation costs for solving and rendering of the application.
Massively Multi-user On line applications (MMOs) allow many users to simultaneously use an application such as real-world phenomena simulator, immersive applications, and so on. Similarly, Massively Multi-user Online Games (MMOG) allow many garners to play simultaneous a video game. MMOs and MMOGs notably rely on computer networks, e.g. the Internet, for allowing the users or garners to connect to the applications or video games. Throughout this specification, the word “application” and “video games” will be understood as to be synonymous, and the terms MMO and MMOG will be indifferently used.
MMOs involve complex and large virtual environments which are desired to be rendered in as much detail as possible, in as close to real time as possible, in order to provide users or game players with a more realistic experience. MMOs are specifically designed for the representation and the manipulation of 3D scenes, and are typically used on the end-user's computer for applications that require interactive, sequential, real-time 3D scene generation. As the user interacts with the 3D scene, the computer redraws the 3D representations rapidly enough to convey to the user the sense of a continuous, ongoing reality in which the user is participating. The scene is composed of many separate objects that can be manipulated by user when interacting with the 3D scene. Thus, MMOs involve large data volumes, high data rates and high data complexity is generally required in order to manage large numbers of users participating in real time in a spatially complex and highly detailed virtual environment.
MMOs are typically used for simulating real-world phenomena within computer models; for instance, Multi-Body Rigid Dynamics, Human Simulation, Cloth Simulation, Particle Simulation. Simulations require accurate data and algorithms that describe real-world phenomena, such as the physical properties (strength, elasticity, etc.) of the materials used in a manufacturing process and the product to create a simulation of the process and a simulation of a product in use. 3D CAD/CAM (Computer Aided Design, Computer Aided Manufacturing) tools allow to create 3D representations of the product or component parts. MMO is also referred to as 3D experience, that is, a virtual environment in which engineers study the behaviors of objects; typically, the simulated environment is an industry environment. The expressions “3D scene” and “3D experience” are synonyms.
MMO's, just like MMOG's, must be scalable to dynamically adapt to the perpetually changing work-load, maintaining thus real-time performance. Scalability notably comprises the number of users that can simultaneously use the application, the number of computing resources for computing the simulations, the number of simultaneous interactions between objects of the 3D scene allowed by the application, and so on.
For MMOG's, the number of users may vary significantly, as well as the positional and graphical attributes of all contained dynamic objects; the dynamic objects are objects likely to move in the scene. Nevertheless, the surrounding scenery is set once for all and the typology of dynamic objects and the supported behavior classes are predefined, before the game starts. Said otherwise, 3D scenes in MMOGs comprise a number of predetermined characteristics that strongly limit the needs of computing resources; thus improving scalability. Forecasting the needs of computing resources is thus possible.
On the contrary, for advanced MMOs, the scenery and population typology of the 3D scene can evolve and enrich, especially while application is running. Indeed, MMOs aim at simulating real-world phenomena, wherein the behavior of objects is dynamic and excludes predefined behavior classes. Consequently, 3D scenery in MMOs cannot use predefined characteristics as for MMOGs.
Thus, even if a 3D Experience has the same kind of real-time and massiveness constraints as MMOG, it has a specific and stringent requirement for far more sophisticated, realistic and accurate physical behaviors, therefore demanding computational power.
One single computing resource cannot cope with all the solving computations in real-time, and for that reason parallelization techniques are required. In few words, the 3D Experience is partitioned into so called zones (also referred to as parts), each of the zones dealing with a specific spatial region of the 3D Experience. The size of these zones is important as it determines whether or not the zones can be computed by a computing resource in real-time. The way a 3D scene (also referred to as 3D experience) is divided into parts is primordial, that is, how the zones are delimited.
The most important requirement when delimiting the zones is that the simulation of each zone always induces a load strictly below 100% of the computing resource to achieve real-time; for instance, below 95% to keep a security margin. There is almost an infinite number of zones suitable for the 3D Experience, but few comes up with the optimal, i.e. smallest number of parts, for which the very same number of computing resources will be sufficient to run simulation in real-time. Performing this selection manually is an enormous time consuming task and it is not efficient as all solutions cannot not manually be explored; thus, the best solutions with the smallest number of zones cannot be obtained within a reasonable time frame when their selection is manually performed.
This problem can be formulated as a continuous problem, where parameters characterizing the solutions are continuously and simultaneously tuned to explore all possibilities, searching the one which fits the best the criteria. When applicable, this option is the most efficient and best quality technique. However, few characterizations (e.g. the number or parts, the number of border points in case they are chosen to be polygons . . . ) are not continuous by nature, and the so usual associated techniques need additional expensive artefacts and turn out to be impracticable to solve this problem.
Within this context, there is still a need for an improved method, computer program, and system for improving the partitioning a 3D scene into a plurality of zones that are processed by computing resources.